A content-addressable memory (CAM), a type of semiconductor memories, is used as a high-speed and low-power functional memory. The CAM executes the lookup-table function that compares an input search word with a table of stored words, and returns the matching word at high speed by a fully parallel equality-search manner.
The CAM is used for applications such as parametric curve extraction (Non-patent Literature 1), the Hough transformation used by the feature extraction method for digital image processing and conversion (Non-patent Literature 2), the Lempel-Ziv compression, which is one of data compression algorithms (Non-patent Literature 3), the human body communication controller (Non-patent Literature 4), the periodic event generator (Non-patent Literature 5), the cache memory (Non-patent Literature 6), and the virus-detection processor (Non-patent Literature 7).
At present, CAMs are mainly used for the packet control by network routers and network switches (Non-patent literatures 8 to 11).
FIG. 18 is a block diagram showing the structure of the CAM of the prior art. As shown in FIG. 18, the CAM 100 of the prior art includes: an input controller 102, word blocks 103 namely memory areas, and an encoder 104. An input search word is transmitted from search lines (SL) to a block (also called a table) 103 of stored words. The number of bits in the CAM 100 usually ranges from 36 to 144 bits. The typical CAM 100 employs a table size ranging between a few hundred to 32K entries. Each entry or word circuit contains several dozens of CAM cells. Each word block 103 has a match line (ML) that indicates whether the search word and stored word are the same or different.
The comparison result of each CAM cell with an input-search bit is determined by whether a pass transistor in the CAM cell attached to the match line (ML) is in ON or OFF state. MLs are connected to the encoder 104. The encoder 104 generates a binary match location (address) corresponding to the ML that is in the match state.
The word blocks or word circuits are normally implemented based on the dynamic logic (Non-patent Literature 12), and are classified into NOR-type (Non-patent Literature 12) and NAND-type (Non-patent Literatures 13 to 15) ones.
In the NOR-type word circuit, since the pass transistors of the NOR-type CAM cells are connected between the ML and the ground line in parallel, the word circuit operates at high speed. Since most of the stored words mismatch the input search word in the CAM, most of the word circuits are in the mismatch state. Hence, the mismatched word circuit discharges the ML capacitance in the NOR-type cell frequently, and thus consumes large power.
The NOR-type CAM cell operates at high speed but consumes large power. To decrease power dissipation of the MLs with low noise immunity, the low-voltage-swing approaches using the current-mode circuits have been proposed (Non-patent Literatures 16 and 17).
In contrast, with a NAND-type CAM cell, since pass transistors are connected between the MLs and the ground line in series in the NAND-type word circuit, the word circuit operates at medium speed. Since the matched word circuits only discharge their ML capacitances, the NAND-type word circuits consume less power than those of the NOR-type word circuits.
The NAND-type CAM cell consumes less power, but operates at medium speed. Hence, to improve the throughput of the NAND-type CAM cell, the pseudo-footless clock-and-data precharged dynamic (PF-CDPD) gate has been proposed (Non-patent Literatures 14 and 15).
In the conventional synchronous CAM, the next search word is assigned after the current search is completed. The throughput of the conventional synchronous CAM is restricted by the number of bits of the CAM word because the worst-case delay of the match operation is usually proportional to the number of bits of the word.
The CAM performs search among the memory cell for storing several hundred or more words and the input data in parallel, and outputs the address of matched words. The whole of the conventional synchronous CAM is collectively controlled using clock signals, and its speed is determined by the overall delay based on the bit length of the word circuit. In IPv6, namely the next-generation Internet protocol (communication procedure), the bit length of the word reaches as long as 144 bits or longer, thus causing the speed of the CAM to decrease. Furthermore, due to increase in network traffic in recent years, the number of entries to be stored has been increased, hence the power consumption is increasing.
As the conventional CAM word circuit method, the method of segmenting the word circuit to decrease power consumption is known. With this method, by segmenting the word circuit, the search is performed with initial several bits first, the match or the mismatch state is judged, and thus by stopping the operation of the most of the remaining word circuits, the decrease in power consumption was attempted. With this method, however, it is necessary to add a sense amplifier, etc. between segments, which causes delay to increase. This delay of the entire word circuit is determined by the sum total of the delay of each segment and that of each sense amplifier.
As a method of achieving high-speed operation while maintaining the effect of decreasing power consumption of this segmentation method, the circuit using a pipeline has been proposed at the architecture level to improve the throughput of the CAM cell (Non-patent Literatures 18 and 19).